﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Queues;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Utils.Backtracers
{
    public class Backtracer<T> : IBacktracer<T,T>
    {
        private readonly IMap<T, T> _backpointers;
        private readonly Func<Lists.IList<T>> _createList;
        private readonly Func<ILifo<T>> _createLifo;

        public Backtracer(IEnumerable<KeyValuePair<T,T>> backpointers, Func<Lists.IList<T>> createList = null, Func<ILifo<T>> createLifo = null,
            Func<IEnumerable<KeyValuePair<T,T>>,IMap<T,T>> createMap = null)
        {
            if ( backpointers is IMap<T,T>)
            {
                _backpointers = (IMap<T, T>) backpointers;
            }
            else
            {
                createMap = createMap ?? (it => AlgoritmiaFactory.Maps<T, T>.BuildDefault(it));
                _backpointers = createMap(backpointers);
            }
            
            _createList = createList ?? ( () => AlgoritmiaFactory.Lists<T>.Default);
            _createLifo = createLifo ?? ( () => AlgoritmiaFactory.Lifos<T>.Default);
        }


        #region IBacktracer<T,TResult> Members

        public Lists.IList<T> Backtrace(T target, Func<T,IMap<T,T>,T> selector = null,EqualityComparison<T> equalityComparison = null)
        {
            if ( !_backpointers.Contains(target) )
                throw new ArgumentException(String.Format("Element {0} is not contained on the backpointers provided", target));

            equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            ILifo<T> lifo = _createLifo();
            lifo.Push(target);
            T current = _backpointers[target];

            while ( !equalityComparison(current,target) )
            {
                target = current;
                lifo.Push(current);
                current = _backpointers[target];
            }

            var list = _createList();

            while ( lifo.Count > 0 )
            {
                list.Add(lifo.Pop());
            }

            return list;
        }

        #endregion
    }
}
